package leetcode101.sort;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code1
 * @Description 215. Kth Largest Element in an Array
 * Given an integer array nums and an integer k, return the kth largest element in the array.
 *
 * Note that it is the kth largest element in the sorted order, not the kth distinct element.
 *
 *  
 *
 * Example 1:
 *
 * Input: nums = [3,2,1,5,6,4], k = 2
 * Output: 5
 * Example 2:
 *
 * Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
 * Output: 4
 *
 * Constraints:
 *
 * 1 <= k <= nums.length <= 104
 * -104 <= nums[i] <= 104
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-29 16:44
 */
public class Code1 {
    public static void main(String[] args) {
        int[] nums = new int[]{3,2,3,1,2,4,5,5,6};
        int k = 1;
        System.out.println(findKthLargest(nums, nums.length));
    }

    public static int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    public static int quickSelect(int[] arr, int low, int high, int target) {

        if (low < high) {
            int pivot = partition(arr, low ,high);
            if (arr.length - pivot == target) {
                return arr[pivot];
            } else if (arr.length - pivot > target) {
                return quickSelect(arr, pivot + 1, high, target);
            } else {
                return quickSelect(arr, low, pivot - 1, target);
            }
        }
        return arr[low];
    }

    public static int partition(int[] arr, int low ,int high) {
        int temp = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= temp) {
                high--;
            }
            arr[low] = arr[high];
            arr[high] = temp;
            while (low < high && arr[low] <= temp) {
                low++;
            }
            arr[high] = arr[low];
            arr[low] = temp;
        }
        return low;
    }
}
/*
使用快速选择解法
 */